package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 257.二叉树的所有路径
 */
public class BiTree11_BinaryTreePaths {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 3, null, 5);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 二叉树的所有路径
        System.out.println(binaryTreePaths(root));
    }

    /**
     * 递归
     */
    private static List<String> binaryTreePaths(TreeNode root) {
        List<String> pathList = new ArrayList<>();
        preorder(root, "", pathList);
        // preorder2(root, new StringBuilder(), pathList);
        return pathList;
    }


    /**
     * 思路1：递归，用 String 保存路径字符串
     * 每次递归调用时，都会将当前节点的值拼接到父节点的路径字符串上。
     */
    private static void preorder(TreeNode root, String pathString, List<String> pathList) {
        if (root == null) {
            return;
        }
        // 叶子节点，保存路径到结果列表中
        if (root.left == null && root.right == null) {
            pathList.add(pathString + root.val);
            return;
        }
        // 保存当前节点的路径字符串
        String nodePathString = pathString + root.val + "->";
        // 递归遍历左右子树
        preorder(root.left, nodePathString, pathList);
        preorder(root.right, nodePathString, pathList);
    }

    /**
     * 思路2：递归，用 StringBuilder 保存路径字符串
     * 每次递归调用时，都会创建一个新的 StringBuilder 实例，该实例包含到当前节点为止的路径字符串。
     */
    private static void preorder2(TreeNode root, StringBuilder sb, List<String> pathList) {
        if (root == null) {
            return;
        }
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            pathList.add(sb.toString());
            return;
        }
        sb.append("->");
        preorder2(root.left, new StringBuilder(sb), pathList);
        preorder2(root.right, new StringBuilder(sb), pathList);
    }

    /**
     * 思路3：迭代，用两个队列分别保存节点和路径
     */
    private static List<String> binaryTreePaths2(TreeNode root) {
        // 叶子节点路径列表
        List<String> pathList = new ArrayList<>();
        if (root == null) {
            return pathList;
        }
        // 两个队列：分别保存节点和路径
        Queue<TreeNode> nodes = new LinkedList<>();
        Queue<String> paths = new LinkedList<>();
        // 根节点和其路径初始化
        nodes.offer(root);
        paths.offer(root.val + "");
        while (!nodes.isEmpty()) {
            // 出队节点和路径
            TreeNode node = nodes.poll();
            String path = paths.poll();
            // 只将叶子节点的路径添加到结果列表中
            if (node.left == null && node.right == null) {
                pathList.add(path);
                continue;
            }
            // 左右子树节点和其路径入队
            if (node.left != null) {
                nodes.offer(node.left);
                paths.offer(path + "->" + node.left.val);
            }
            if (node.right != null) {
                nodes.offer(node.right);
                paths.offer(path + "->" + node.right.val);
            }
        }
        return pathList;
    }

}
